Структура података за представљање дисјунктних подскупова (union-find)

Понекад је потребно одржавати у програму неколико дисјунктних подскупова одређеног скупа, при чему је моћи за дати елемент ефикасно пронаћи ком скупу припада (ова операција се зове find) и ефикасно спојити два задата подскупа у нови, већи подскуп (ту операцију називамо union). Помоћу операције find лако можемо за два елемента проверити да ли припадају истом подскупу тако што за сваки од њих пронађемо ознаку подскупа и проверимо да ли су оне једнаке.

Једна могућа имплементација је да се одржава пресликавање свако еллемента у ознаку подскупа којем припада. Ако претпоставимо да су сви елементи нумерисали бројевима од \(0\) до \(n-1\), онда ово пресликавање можемо реализовати помоћу обичног низа где се на позицији сваког елемента налази ознака подскупа којем он припада (ако елементи нису нумерисани бројевима, могли бисмо користити мапу уместо низа). Операција find је тада тривијална (само се из низа прочита ознака подскупа) и сложеност јој је \(O(1)\). Операција union је много спорија, јер захтева да се ознаке свих елемената једног подскупа промене у ознаке другог, што захтева да се прође кроз читав низ и сложености је \(O(n)\).

int id[MAX_N];
int n;

void inicijalizuj() {
  for (int i = 0; i < n; i++)
    id[i] = i;
}

int predstavnik(int x) {
   return id[x];
}

int u_istom_podskupu(int x, int y) {
  return predstavnik(x) == predstavnik(y);
}

void unija(int x, int y) {
  int idx = id[x], idy = id[y];
  for (int i = 0; i < n; i++)
    if (id[i] == idx)
      id[i] = idy;
}

Кључна идеја је да елементе не пресликавамо у ознаке подскупова, већ да поскупове чувамо у облику дрвета тако да сваки елемент сликамо у његовог родитеља у дрвету. Корене дрвета ћемо сликати саме у себе и сматрати их ознакама подскупова. Дакле, да бисмо на основу произвољног елемента сазнали ознаку подскупа ком припада, потребно је да прођемо кроз низ родитеља све док не стигнемо до корена. Нагласимо да су у овим дрветима показивачи усмерени од деце ка родитељима, за разлику од класичних дрвета где показивачи указују од родитеља ка деци.

Унију можемо вршити тако што корен једног подскупа усмеримо ка корену другог.

Први алгоритам одговара ситуацији у којој особа која промени адреду обавештава све друге особе о својој новој адреси. Други одговара ситуацији у којој само на старој адреси оставља информацију о својој новој адреси. Ово, наравно, мало успорава доставу поште, јер се мора прећи кроз низ преусмеравања, али ако тај низ није предугачак, може бити значајно ефикаснији од првог приступа.

int roditelj[MAX_N];
int n;

void inicijalizuj() {
  for (int i = 0; i < n; i++)
    roditelj[i] = i;
}

int predstavnik(int x) {
  while (roditelj[x] != x) 
    x = roditelj[x];
  return x;
}

void unija(int x, int y) {
  int fx = predstavnik(x), fy = predstavnik(y);
  roditelj[fx] = fy;
}

Сложеност претходног приступа зависи од тога колико су дрвета којима се представљају подскупови уравнотежена. У најгорем случају се она могу издегенерирати у листу и тада је сложеност сваке од операција \(O(n)\). Илуструјмо ово једним примером.

0  1  2  3  4  5  6  7

unija 7 6

0  1  2  3  4  5  6  6

unija 6 5

0  1  2  3  4  5  5  6

unija 5 4

0  1  2  3  4  4  5  6

unija 4 3

0  1  2  3  3  4  5  6

unija 3 2

0  1  2  2  3  4  5  6

unija 2 1

0  1  1  2  3  4  5  6

unija 1 0

0  0  1  2  3  4  5  6

Упит којим се тражи представник скупа којем припада елемент 7 се реализује низом корака којима се прелази преко следећих елемената 7,6,5,4,3,2,1,0. Иако се ово чини горим од претходног приступа, где је бар проналажење подскупа коштало \(O(1)\) када су дрвета уравнотежена, тада је сложеност сваке од операција \(O(\log{n})\) и централни задатак да би се на овој идеји изградила ефикасна структура података је да се на неки начин обезбеди да дрвета остану уравнотежена. Кључна идеја је да се приликом измена (а она се врше само у склопу операције уније), ако је могуће, обезбеди да се висина дрвета којим се представља унија не повећа у односу на висине појединачних дрвета која представљају скупове који се унирају (висину можемо дефинисати као број грана на путањи од тог чвора до њему најудаљенијег листа). Приликом прављења уније, имамо слободу избора корена ког ћемо усмерити ка другом корену. Ако се увек изабере да корен плићег дрвета усмеравамо ка дубљем, тада ће се висина уније повећавати само ако су оба дрвета кој унирамо исте висине. Висину дрвета можемо одржавати у посебном низу који ћемо из разлога који ће бити касније објашњени назвати rang.

int roditelj[MAX_N];
int n;
int rang[MAX_N];

void inicijalizuj() {
  for (int i = 0; i < n; i++) {
    roditelj[i] = i;
    rang[i] = 0;
  }
}

int predstavnik(int x) {
  while (roditelj[x] != x) 
    x = roditelj[x];
  return x;
}

void unija(int x, int y) {
  int fx = predstavnik(x), fy = predstavnik(y);
  if (rang[fx] < rang[fy])
     roditelj[fx] = fy;
  else if (rang[fy] < rang[fx])
     roditelj[fy] = fx;
  else {
     roditelj[fx] = fy;
     rang[fy]++;
  }
}

Покажимо рад алгоритма на једном примеру. Подскупове ћемо представљати дрветима.

1  2  3  4  5  6  7  8

unija 1 2

1  3  4  5  6  7  8
2

unija 6 7

1  3  4  5  6  8
2           7

unija 4 7

1  3  5     6    8
2         4   7

unija 5 8

1  3    6     8
2     4   7   5

unija 1 3

  1       6     8
2   3   4   7   5

unija 5 4

  1        6
2   3   4  7  8
              5
              
unija 3 7

       6
  1  4  7  8
2   3      5

Докажимо индукцијом да се у дрвету чији је корен на висини \(h\) налази бар \(2^h\) чворова. База је почетни случај у коме је сваки чвор свој представник. Висина свих чворова је тада нула и сва дрвета имају \(2^0=1\) чвор. Покажимо да свака унија одржава ову инваријанту. По индуктивној хипотези претпостављамо да оба дрвета која представљају подскупове који се унирају имају висине \(h_1\) и \(h_2\) и бар \(2 ^{h_1}\) и \(2^{h_2}\) чворова. Уколико се унирањем висина не повећа, инваријанта је очувана јер се број чворова повећао. Једини случај када се повећава висина уније је када је \(h_1 = h_2\) и тада обједињено дрво има висину \(h = h_1 + 1 = h_2 + 1\) и бар \(2^{h_1} + 2^{h_2} = 2^h\) чворова. Тиме је тврђење доказано. Дакле, сложеност сваке операције проналаска представника у скупу од \(n\) чворова је \(O(\log{n})\), а пошто унирање након проналажења представника врши још само \(O(1)\) операција, и сложеност налажења уније је \(O(\log{n})\).

Рецимо и да је уместо висине могуће одржавати број чворова у сваком од подскупова. Ако увек усмеравамо представника мањег ка представнику већег подскупа, поново ћемо добити логаритамску сложеност најгорег случаја за обе операције. Ово важи зато што и овај начин прављења уније гарантује да не можемо имати високо дрво са малим бројем чворова. Да би се добило дрво висине 1, потребна су најмање два чвора; да би се добило дрво висине 2 најмање четири чвора (јер се спајају два дрвета висине 1 која имају бар по два чвора). Да би се добило дрво висине \(h\) потребно је најмање \(2^h\) чворова. Одавде следи да ће висине свих дрвета у овој структури бити висине \(O(\log{n})\).

Иако је ова сложеност сасвим прихватљива (сложеност проналажења \(n\) унија је \(O(n \log{n})\)), може се додатно побољшати врло једноставном техником познатом као компресија путање. Наиме, приликом проналажења представника можемо све чворове кроз које пролазимо усмерити према корену. Један начин да се то постигне је да се након проналажења корена, поново прође кроз низ родитеља и сви показивачи усмере према корену.

int predstavnik(int x) {
  int koren = x;
  while (koren != roditelj[koren])
    koren = roditelj[koren];
  while (x != koren) {
    int tmp = roditelj[x];
    roditelj[x] = koren;
    x = tmp;
  }
  return koren;
}

За све чворове који се обилазе од полазног чвора до корена, дужине путања до корена се након овога смањују на 1, међутим, као што примећујемо, низ рангова се не мења. Ако рангове тумачимо као број чворова у подскупу, онда се приликом компресије путање та статистика и не мења, па је поступак коректан. Ако рангове тумачимо као висине, јасно је да приликом компресије путање низ висина постаје неажуран. Међутим, интересантно је да ни у овом случају нема потребе да се он ажуририа. Наиме, бројеви који се сада чувају у том низу не представљају више висине чворова, већ горње границе висина чворова. Ови бројеви се надаље сматрају ранговима чворова, тј. помоћним подацима који нам помажу да преусмеримо чвовове приликом унирања. Показује се да се овим не нарушава сложеност најгорег случаја и да функција наставља коректно да ради.

У претходној имплементацији се два пута пролази кроз путању од чвора до корена. Ипак, сличне перформансе се могу добити и само у једном пролазу. Постоје два начина на који се ово може урадити: један од њих је да се сваки чвор усмери ка родитељу свог родитеља. За све чворове који се обилазе од полазног чвора до корена, дужине путања до корена се након овога смањују двоструко, што је довољно за одличне перформансе.

int predstavnik(int x) {
  while (x != roditelj[x]) {
    tmp = roditelj[x];
    roditelj[x] = roditelj[roditelj[x]];
    x = tmp;
  }
  return x;
}

Други начин подразумева да се приликом проласка од чвора ка корену сваки други чвор на путањи усмери ка родитељу свог родитеља.

int predstavnik(int x) {
  while (x != roditelj[x]) {
    roditelj[x] = roditelj[roditelj[x]];
    x = roditelj[x];
  }
  return x;
}

Приметимо да је овим додата само једна линија кода у првобитну имплементацију. Овом једноставном променом амортизована сложеност операција постаје само \(O(\alpha(n))\), где је \(\alpha(n)\) инверзна Акерманова функција која страшно споро расте. За били који број \(n\) који је мањи од броја атома у целом универзуму важи да је \(\alpha(n) < 5\), тако да је време практично константно.